package Offer.offer;

/**
 * 数组中出现次数超过一半的数字
 *
 * @author leiwenkang
 * @date 2020/4/7
 */
public class Test29数组中出现次数超过一半的数字 {
    //基于快排partion函数
    public static int moreThanHalfNum(int[] array) {
        if (array == null || array.length == 0) {
            throw new RuntimeException("数组非法！");
        }
        int low = 0;
        int high = array.length - 1;
        int mid = (low + high) >> 1;
        int pos = partition(array, low, high);
        while (pos != mid) {
            if (pos < mid) {
                pos = partition(array, pos + 1, high);
            } else {
                pos = partition(array, low, pos - 1);
            }
        }
        if (!checkMoreThanHalf(array, array[pos])){
            System.out.println("不存在!");
            return -1;
        }
        return array[pos];
    }

    private static int partition(int[] array, int low, int high) {
        int value = array[low];
        while (low < high) {
            while (low < high && array[high] >= value) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= value) {
                low++;
            }
            array[high] = array[low];
        }
        array[high] = value;
        return high;
    }

    private static boolean checkMoreThanHalf(int[] array, int num) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == num) {
                count++;
            }
        }
        if (2 * count > array.length) {
            return true;
        }
        return false;
    }
}
